//Labels is the binary image

#include "limits.h"

__global__ void initLabels(unsigned int* Labels,int widthImage,int heightImage)
{
    int x = blockIdx.x *blockDim.x + threadIdx.x;
    int y = blockIdx.y *blockDim.x + threadIdx.y;
    int index=y*widthImage+x;


    if(index==0)Labels[index]*=1;
    else{
    Labels[index]*=index;}

}

__global__ void Scanning(unsigned int* Labels,int widthImage,int heightImage,bool* IsNotDone)
{
    int x = blockIdx.x *blockDim.x + threadIdx.x;
    int y = blockIdx.y * blockDim.y + threadIdx.y;

    unsigned int aPos=y*widthImage+x;
    unsigned int newLabel=Labels[aPos];

    unsigned int left;
    unsigned int right;
    unsigned int up;
    unsigned int upleft;
    unsigned int upright;
    unsigned int down;
    unsigned int downleft;
    unsigned int downright;
    unsigned int minLabel=UINT_MAX;
    if(x<widthImage &&y<heightImage)
    {

        if(newLabel)
        {
            if(y!=0&&x!=0)upleft=Labels[aPos-widthImage-1];
            else {
                upleft=0;
            }
            if(y!=0&&x!=(widthImage-1))upright=Labels[aPos-widthImage+1];
            else {
                upright=0;
            }
            if(x!=0&&y!=(heightImage-1))downleft=Labels[aPos+widthImage-1];
            else {
                downleft=0;
            }
            if(x!=(widthImage-1)&&y!=(heightImage-1))downright=Labels[aPos+widthImage+1];
            else {
                downright=0;
            }
            if(x!=0)
            {
                left=Labels[aPos-1];
            }
            else
            {
                left=0;
            }
            if(x!=widthImage-1)
            {
                right=Labels[aPos+1];
            }
            else
            {
                right=0;
            }
            if(y!=0)
            {
                up=Labels[aPos-widthImage];
            }
            else
            {
                up=0;
            }
            if(y!=heightImage-1)
            {
                down=Labels[aPos+widthImage];
            }
            else
            {
                down=0;
            }
            if(left)minLabel=left;
            if(up&&up<minLabel)minLabel=up;
	    if(down&&down<minLabel)minLabel=down;
            if(right&&right<minLabel)minLabel=right;
            if(upright&&upright<minLabel)minLabel=upright;
             if(downleft&&downleft<minLabel)minLabel=downleft;
             if(downright&&downright<minLabel)minLabel=downright;
          if(upleft&&upleft<minLabel)minLabel=upleft;
            if(minLabel<newLabel)
            {
                unsigned int newLabel2=Labels[newLabel];
                Labels[newLabel]=(unsigned int)min(newLabel2,minLabel);
                IsNotDone[0]=true;
            }
        }
    }
}
inline
__device__ int findRoot(unsigned int* buf,unsigned int x) {
    int nextX;
    do {
        nextX = x;
        x = buf[nextX];
    } while (x < nextX);
    return x;
}

__global__ void Analysis(unsigned int* Labels,int widthImage,int heightImage)
{
    int x = blockIdx.x *blockDim.x + threadIdx.x;
    int y = blockIdx.y * blockDim.y + threadIdx.y;

    unsigned int aPos=y*widthImage+x;
    unsigned int newLabel=Labels[aPos];
     if(x<widthImage &&y<heightImage)
     {
        if(newLabel)
        {
            unsigned int r=Labels[newLabel];
            unsigned int rootValue=findRoot(Labels, r);
            Labels[aPos]=rootValue;
        }
     }
}

__global__ void reIndex(unsigned int* Labels,int widthImage,int heightImage,unsigned int *input_array,unsigned int array_size)
{
    int x = blockIdx.x *blockDim.x + threadIdx.x;
    int y = blockIdx.y * blockDim.y + threadIdx.y;

    unsigned int aPos=y*widthImage+x;
    unsigned int newLabel=Labels[aPos];
   
    unsigned int a= 1;
    unsigned int b= array_size-1;
    unsigned int mid;
     if(x<widthImage &&y<heightImage&&newLabel)
     {
         
  do{
    mid= (a+b)/ 2;
    if (newLabel > input_array[mid]) {a = mid + 1;}
    else if(newLabel < input_array[mid]){b= mid - 1;}
    else{break;}
  }while (1) ;      
	Labels[aPos]=mid;
}
}

